package WEEK_191;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

import LCommon.TreeNode;

public class Solution {
	public int maxProduct(int[] nums) {
		Arrays.sort(nums);
		return (nums[nums.length - 1] - 1) * (nums[nums.length - 2] - 1);
	}

	int mod = 1000000007;

	public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
		long hMax = getMaxGetter(h, horizontalCuts) % mod;
		long wMax = getMaxGetter(w, verticalCuts) % mod;
		return (int) ((hMax * wMax) % mod);

	}

	private long getMaxGetter(int num, int[] arr) {
		Arrays.sort(arr);
		if (arr.length > 0) {

			int max = arr[0];

			for (int i = 1; i < arr.length; i++) {
				int temp = arr[i] - arr[i - 1];
				max = Math.max(max, temp);
			}
			return Math.max(max, num - arr[arr.length - 1]);
		} else {
			return num;
		}

	}

	public int minReorder(int n, int[][] connections) {
		Set<Integer> available = new HashSet<Integer>();
		available.add(0);
		int change = 0;
		for (int[] point : connections) {
			if (available.contains(point[1])) {
				available.add(point[0]);
			} else {
				change++;
				available.add(point[1]);
			}
		}
		return change;
	}
}
